EVENTO
Algoritmos Quânticos para o Problema do Subgrupo Oculto Não Abeliano
Tipo de evento: Defesa de Tese de Doutorado
Desde o surgimento do consagrado Algoritmo de Shor para a fatoração de números primos, a pesquisa de algoritmos quânticos tem recebido bastante atenção da comunidade científica. Uma das linhas de interesse desta área é a que trata do Problema do Subgrupo Oculto, PSO. Inicialmente se abordou este problema em grupos abelianos, resolvendo-o eficientemente através de um algoritmo quântico. Depois disso, a pesquisa avançou para o PSO em grupos não abelianos, onde desperta grande interesse, pois uma solução eficiente do PSO em certos grupos não abelianos implica em soluções eficientes de problemas como o Problema do Isomorfismo de Grafos e o Problema do Menor Vetor de um Reticulado. É no contexto do PSO não abeliano que desenvolvemos nossa pesquisa para a tese de doutorado. Em nosso trabalho, resolvemos eficientemente certas instancias do PSO não abeliano, atacando o problema no produto semidireto dos grupos cíclicos e , e também no produto semidireto de por , onde p é um número primo ímpar e N, r e s são inteiros positivos que satisfazem a certas propriedades. A estratégia que empregamos para a solução se utiliza de elementos já consolidados na literatura da área, como a Transformada de Fourier abeliana e o PSO abeliano, com um argumento que explora a estrutura algébrica do grupo onde atacamos o problema. O resultado dessa combinação é um algoritmo quântico eficiente para a solução do PSO nos grupos acima citados.
Data Início: 13/03/2008 Hora: 14:00 Data Fim: 13/03/2008 Hora: 17:30
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Carlos Magno Martins Cosme - Universidade Federal dos Vales Gequitinhonha - UFVJM
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Carlile Campos Lavor - Universidade Estadual de Campinas - IMECC/UNICAMP Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC Guilherme Augusto de La Rocque Leal - IM-UFRJ - UFRJ Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: Marcelo Dutra Fragoso - Laboratório Nacional de Computação Científica - LNCC Rubens Viana Ramos - DETIF-UFC - DETIF-UFC
